package middle;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;
import util.PrintUtils;

public class Solution_785 {

    public boolean isBipartite(int[][] graph) {
        Map<Integer, Boolean> map = new HashMap<>(101);
        LinkedList<Integer> list = new LinkedList<>();

        for (int j = 0; j < graph.length; j++) {
            if (map.containsKey(j)) {
                continue;
            }
            list.add(j);
            map.put(j, true);
            boolean flag = false;
            while (!list.isEmpty()) {
                int count = list.size();
                for (int i = 0; i < count; i++) {
                    Integer poll = list.poll();
                    int[] ints = graph[poll];
                    for (int anInt : ints) {
                        if (map.containsKey(anInt)) {
                            if (map.get(anInt) != flag) {
                                return false;
                            }
                        } else {
                            map.put(anInt, flag);
                            list.add(anInt);
                        }
                    }
                }
                flag = !flag;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution_785 model = new Solution_785();
        System.out.println(model.isBipartite(new int[][]{{1,2,3},{0,2},{0,1,3},{0,2}}));
        System.out.println(model.isBipartite(new int[][]{{1,3},{0,2},{1,3},{0,2}}));
        System.out.println(model.isBipartite(new int[][]{{},{2,4,6},{1,4,8,9},{7,8},{1,2,8,9},{6,9},{1,5,7,8,9},{3,6,9},{2,3,4,6,9},{2,4,5,6,7,8}}));
//        PrintUtils.transfer("[[],[2,4,6],[1,4,8,9],[7,8],[1,2,8,9],[6,9],[1,5,7,8,9],[3,6,9],[2,3,4,6,9],[2,4,5,6,7,8]]");
    }
}
